import { ICompareFunction, defaultCompare, Compare, swap } from '../../util';

/**
 * 下移操作
 * 如果compareFn是升序，array[left]更大最合适
 * 如果compareFn是降序，array[left]更小最合适
 * 所以使用Compare.LESS_THAN
 */
function heapify(array: any[], index: number, heapSize: number, compareFn: ICompareFunction<any>) {
    let largest = index; // 当前节点
    const left = getLeftIndex(index); // 左子节点
    const right = getRightIndex(index); // 右子节点

    // 有左子节点，并且左子节点比当前节点更适合
    if (left < heapSize && compareFn(array[index], array[left]) === Compare.LESS_THAN) {
        largest = left;
    }
    // 有右子节点，并且右子节点比当前节点和左子节点更适合
    if (right < heapSize && compareFn(array[largest], array[right]) === Compare.LESS_THAN) {
        largest = right;
    }

    if (largest !== index) { // 还是自己的话就不用交换
        swap(array, index, largest); // 交换值
        heapify(array, largest, heapSize, compareFn); // 继续下移
    }
}
/**
 * 左子节点的index
 */
function getLeftIndex(index: number): number {
    if (index < 0) {
        return undefined;
    }
    // 每一层都是2的倍数，也就是父节点和子节点是两倍的关系
    return index * 2 + 1;
}
/**
 * 右子节点的index
 */
function getRightIndex(index: number): number {
    if (index < 0) {
        return undefined;
    }
    // 每一层都是2的倍数，也就是父节点和子节点是两倍的关系
    return index * 2 + 2;
}
/**
 * 父节点的index
 */
function getParentIndex(index: number): number {
    if (index <= 0) {
        return undefined;
    }
    // 每一层都是2的倍数，也就是父节点和子节点是两倍的关系
    return Math.floor((index - 1) / 2);
}
/**
 * 构建最大堆或最小堆
 * compareFn为defaultCompare，构造最大堆
 * compareFn为reverseCompare(defaultCompare)，构造最小堆
 */
function buildHeap(array: any[], compareFn: ICompareFunction<any>) {
    /*
        从“最后一项的父节点”开始往上，依次进行下移处理
        因为要处理当前节点的左右子节点，而左右子节点是(length - 1)，
        用getParentIndex反推，其实就是“最后一项的父节点”
    */
    const maxIndex = getParentIndex(array.length - 1);
    for (let i = maxIndex; i >= 0; i --) {
        // 下移处理
        heapify(array, i, array.length, compareFn);
    }
    return array;
}
/**
 * 堆排序
 * compareFn为defaultCompare，构造最大堆，相应的也要输出是升序的
 * compareFn为reverseCompare(defaultCompare)，构造最小堆，相应的也要输出是降序的
 */
export default function heapSort(array: any[], compareFn = defaultCompare) {
    // 先构建一个二叉堆
    buildHeap(array, compareFn);
    // 类似于依次移除根节点，最大堆移除根节点放到数组末尾就是升序的
    let heapSize = array.length;
    while (heapSize > 1) {
        swap(array, 0, -- heapSize);
        heapify(array, 0, heapSize, compareFn);
    }
    return array;
}
